{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Sets of K Non-Overlapping Line Segments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfSets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #大小为 K 的不重叠线段的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一维空间的 <code>n</code> 个点，其中第 <code>i</code> 个点（编号从 <code>0</code> 到 <code>n-1</code>）位于 <code>x = i</code> 处，请你找到 <strong>恰好</strong> <code>k</code> <strong>个不重叠</strong> 线段且每个线段至少覆盖两个点的方案数。线段的两个端点必须都是 <strong>整数坐标</strong> 。这 <code>k</code> 个线段不需要全部覆盖全部 <code>n</code> 个点，且它们的端点 <strong>可以 </strong>重合。</p>\n",
    "\n",
    "<p>请你返回 <code>k</code> 个不重叠线段的方案数。由于答案可能很大，请将结果对 <code>10<sup>9</sup> + 7</code> <strong>取余</strong> 后返回。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/17/ex1.png\" style=\"width: 179px; height: 222px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>n = 4, k = 2\n",
    "<b>输出：</b>5\n",
    "<strong>解释：\n",
    "</strong>如图所示，两个线段分别用红色和蓝色标出。\n",
    "上图展示了 5 种不同的方案 {(0,2),(2,3)}，{(0,1),(1,3)}，{(0,1),(2,3)}，{(1,2),(2,3)}，{(0,1),(1,2)} 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 3, k = 1\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>总共有 3 种不同的方案 {(0,1)}, {(0,2)}, {(1,2)} 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 30, k = 7\n",
    "<b>输出：</b>796297179\n",
    "<strong>解释：</strong>画 7 条线段的总方案数为 3796297200 种。将这个数对 10<sup>9</sup> + 7 取余得到 796297179 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 5, k = 3\n",
    "<b>输出：</b>7\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 3, k = 2\n",
    "<b>输出：</b>1</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= n <= 1000</code></li>\n",
    "\t<li><code>1 <= k <= n-1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-sets-of-k-non-overlapping-line-segments](https://leetcode.cn/problems/number-of-sets-of-k-non-overlapping-line-segments/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-sets-of-k-non-overlapping-line-segments](https://leetcode.cn/problems/number-of-sets-of-k-non-overlapping-line-segments/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n2', '3\\n1', '30\\n7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        import math\n",
    "        return math.comb(n+k-1, 2*k) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        return math.comb(n+k-1, 2*k) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        return math.comb(n+k-1,k*2)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        return comb(n + k - 1, k << 1) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "\n",
    "        return math.comb(n+k-1,2*k) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        return math.comb(n + k - 1, k * 2) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        return math.comb(n + k -1, 2*k) % (10 ** 9 + 7)\n",
    "    \n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        return math.comb(n + k - 1, k * 2) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        return math.comb(n + k - 1, k * 2) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        return math.comb(n+k-1, 2*k) % (10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        return math.comb(n+k-1, 2*k)%(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import math\n",
    "ha = 10 ** 9 + 7\n",
    "\n",
    "def C(n, m):\n",
    "    if m == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return math.factorial(n) // (math.factorial(m) * math.factorial(n - m))\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(k + 1, 2 * k + 1):\n",
    "            if i <= n:\n",
    "                if i - 3 > 0:\n",
    "                    ans += C(n, i) * C(k - 1, i - k - 1)\n",
    "                else:\n",
    "                    ans += C(n, i)\n",
    "\n",
    "        return ans % ha\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        return comb(n + k - 1, 2 * k) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        return comb(n+k-1,2*k)%int(1e9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return math.comb(n+k-1, 2*k) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        M = 10 ** 9 + 7\n",
    "\n",
    "        def gcd(a: int, b: int) -> int:\n",
    "            while b != 0:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "\n",
    "        n += k - 1\n",
    "        k *= 2\n",
    "        if k * 2 > n:\n",
    "            k = n - k\n",
    "        a = [n - i for i in range(k)]\n",
    "        for x in range(1, k + 1):\n",
    "            m, i = len(a), 0\n",
    "            while x != 1:\n",
    "                g = gcd(x, a[i])\n",
    "                x //= g\n",
    "                a[i] //= g\n",
    "                if a[i] != 1:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    a[i] = a[m-1]\n",
    "                    del a[m-1]\n",
    "                    m -= 1\n",
    "        res = 1\n",
    "        for x in a:\n",
    "            res = res * x % M\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n, k):\n",
    "        return math.comb(n+k-1, 2*k) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        return math.comb(n+k-1, 2*k)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import math\n",
    "ha = 10 ** 9 + 7\n",
    "\n",
    "def C(n, m):\n",
    "    if m == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return math.factorial(n) // (math.factorial(m) * math.factorial(n - m))\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(k + 1, 2 * k + 1):\n",
    "            if i <= n:\n",
    "                if i - 3 > 0:\n",
    "                    ans += C(n, i) * C(k - 1, i - k - 1)\n",
    "                else:\n",
    "                    ans += C(n, i)\n",
    "\n",
    "        return ans % ha\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        \n",
    "        # Calculate factorial and its inverse for n + k using Fermat's Little Theorem\n",
    "        factorial = [1] * (n + k)\n",
    "        inv_factorial = [1] * (n + k)\n",
    "        \n",
    "        for i in range(1, n + k):\n",
    "            factorial[i] = factorial[i-1] * i % MOD\n",
    "        \n",
    "        inv_factorial[n + k - 1] = pow(factorial[n + k - 1], MOD - 2, MOD)\n",
    "        for i in range(n + k - 2, 0, -1):\n",
    "            inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD\n",
    "        \n",
    "        # Calculate combination using factorial and its inverse\n",
    "        def combination(n, r):\n",
    "            if r > n or r < 0:\n",
    "                return 0\n",
    "            return (factorial[n] * inv_factorial[r] % MOD) * inv_factorial[n-r] % MOD\n",
    "        \n",
    "        return combination(n + k - 1, 2 * k) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        return math.comb(n + k - 1, 2 * k) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        mod, ans = 10 ** 9 + 7, 0\n",
    "        for pre in range(k, n):\n",
    "            rest = n - 1 - pre \n",
    "            ans += comb(pre - 1, k - 1) * comb(rest + k, k) % mod \n",
    "        return ans % mod "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [[0] * 2 for _ in range(k + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n):\n",
    "            for j in range(min(i, k), 0, -1):\n",
    "                dp[j][0] = (dp[j][0] + dp[j][1]) % MOD\n",
    "                dp[j][1] = (dp[j][1] + dp[j - 1][0] + dp[j - 1][1]) % MOD\n",
    "        return sum(dp[k]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "\n",
    "        '''\n",
    "        f(i, j): [0, i]放置j段不重叠线段的方案数，考虑以下转移:\n",
    "        最后一个位置不使用: f(i - 1, j)\n",
    "        [i - 1, i]放一条线段：f(i - 1, j - 1)\n",
    "        [i - 2, i]放一条线段: f(i - 2, j - 1)\n",
    "        ……\n",
    "\n",
    "        f(i, j) = f(i - 1, j) + f(i - 1, j - 1) + f(i - 2, j - 1) + …… f(0, j - 1)\n",
    "同样f(i - 1, j) = f(i - 2, j) + f(i - 2, j - 1) + f(i - 3, j - 1) + …… f(0, j - 1)\n",
    "\n",
    "        相减:f(i, j) = 2 * f(i - 1, j) + f(i - 1, j - 1) - f(i - 2, j)\n",
    "        '''\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [[0] * (k + 1) for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            f[i][1] = i * (i + 1) // 2 % MOD\n",
    "            for j in range(2, min(k, i) + 1):\n",
    "                # if j == i:\n",
    "                #     f[i][j] = 1\n",
    "                #     break\n",
    "                f[i][j] = (2 * f[i - 1][j] + f[i - 1][j - 1] - f[i - 2][j]) % MOD\n",
    "        return f[n - 1][k]\n",
    "\n",
    "        # MOD = 10 ** 9 + 7\n",
    "        # @cache\n",
    "        # def f(i, j):\n",
    "        #     if i < j:\n",
    "        #         return 0\n",
    "        #     if i == j:\n",
    "        #         return 1\n",
    "        #     if j == 1:\n",
    "        #         return  i * (i + 1) // 2\n",
    "        #     return (2 * f(i - 1, j) + f(i - 1, j - 1) - f(i - 2, j)) % MOD\n",
    "        # return f(n - 1, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "\n",
    "        '''\n",
    "        f(i, j): [0, i]放置j段不重叠线段的方案数，考虑以下转移:\n",
    "        最后一个位置不使用: f(i - 1, j)\n",
    "        [i - 1, i]放一条线段：f(i - 1, j - 1)\n",
    "        [i - 2, i]放一条线段: f(i - 2, j - 1)\n",
    "        ……\n",
    "\n",
    "        f(i, j) = f(i - 1, j) + f(i - 1, j - 1) + f(i - 2, j - 1) + …… f(0, j - 1)\n",
    "同样f(i - 1, j) = f(i - 2, j) + f(i - 2, j - 1) + f(i - 3, j - 1) + …… f(0, j - 1)\n",
    "\n",
    "        相减:f(i, j) = 2 * f(i - 1, j) + f(i - 1, j - 1) - f(i - 2, j)\n",
    "        '''\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [[0] * (k + 1) for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            f[i][1] = i * (i + 1) // 2 % MOD\n",
    "            for j in range(2, min(k, i) + 1):\n",
    "                if j == i:\n",
    "                    f[i][j] = 1\n",
    "                    break\n",
    "                f[i][j] = (2 * f[i - 1][j] + f[i - 1][j - 1] - f[i - 2][j]) % MOD\n",
    "        return f[n - 1][k]\n",
    "\n",
    "        # MOD = 10 ** 9 + 7\n",
    "        # @cache\n",
    "        # def f(i, j):\n",
    "        #     if i < j:\n",
    "        #         return 0\n",
    "        #     if i == j:\n",
    "        #         return 1\n",
    "        #     if j == 1:\n",
    "        #         return  i * (i + 1) // 2\n",
    "        #     return (2 * f(i - 1, j) + f(i - 1, j - 1) - f(i - 2, j)) % MOD\n",
    "        # return f(n - 1, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "\n",
    "        '''\n",
    "        f(i, j): [0, i]放置j段不重叠线段的方案数，考虑以下转移:\n",
    "        最后一个位置不使用: f(i - 1, j)\n",
    "        [i - 1, i]放一条线段：f(i - 1, j - 1)\n",
    "        [i - 2, i]放一条线段: f(i - 2, j - 1)\n",
    "        ……\n",
    "\n",
    "        f(i, j) = f(i - 1, j) + f(i - 1, j - 1) + f(i - 2, j - 1) + …… f(0, j - 1)\n",
    "同样f(i - 1, j) = f(i - 2, j) + f(i - 2, j - 1) + f(i - 3, j - 1) + …… f(0, j - 1)\n",
    "\n",
    "        相减:f(i, j) = 2 * f(i - 1, j) + f(i - 1, j - 1) - f(i - 2, j)\n",
    "        '''\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [[0] * (k + 1) for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            f[i][1] = i * (i + 1) // 2 % MOD\n",
    "            for j in range(2, min(k, i) + 1):\n",
    "                if j == i:\n",
    "                    f[i][j] = 1\n",
    "                    break\n",
    "                f[i][j] = (2 * f[i - 1][j] + f[i - 1][j - 1] - f[i - 2][j]) % MOD\n",
    "        return f[n - 1][k]\n",
    "\n",
    "        # MOD = 10 ** 9 + 7\n",
    "        # @cache\n",
    "        # def f(i, j):\n",
    "        #     if i < j:\n",
    "        #         return 0\n",
    "        #     if i == j:\n",
    "        #         return 1\n",
    "        #     if j == 1:\n",
    "        #         return  i * (i + 1) // 2\n",
    "        #     return (2 * f(i - 1, j) + f(i - 1, j - 1) - f(i - 2, j)) % MOD\n",
    "        # return f(n - 1, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "\n",
    "        '''\n",
    "        f(i, j): [0, i]放置j段不重叠线段的方案数，考虑以下转移:\n",
    "        最后一个位置不使用: f(i - 1, j)\n",
    "        [i - 1, i]放一条线段：f(i - 1, j - 1)\n",
    "        [i - 2, i]放一条线段: f(i - 2, j - 1)\n",
    "        ……\n",
    "\n",
    "        f(i, j) = f(i - 1, j) + f(i - 1, j - 1) + f(i - 2, j - 1) + …… f(0, j - 1)\n",
    "同样f(i - 1, j) = f(i - 2, j) + f(i - 2, j - 1) + f(i - 3, j - 1) + …… f(0, j - 1)\n",
    "\n",
    "        相减:f(i, j) = 2 * f(i - 1, j) + f(i - 1, j - 1) - f(i - 2, j)\n",
    "\n",
    "        初态：f(i, 1) = C(i + 1, 2) = i * (i + 1) // 2\n",
    "        '''\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [[0] * (k + 1) for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            f[i][1] = i * (i + 1) // 2 % MOD\n",
    "            for j in range(2, min(k, i) + 1):\n",
    "                f[i][j] = (2 * f[i - 1][j] + f[i - 1][j - 1] - f[i - 2][j]) % MOD\n",
    "        return f[n - 1][k]\n",
    "\n",
    "        # MOD = 10 ** 9 + 7\n",
    "        # @cache\n",
    "        # def f(i, j):\n",
    "        #     if i < j:\n",
    "        #         return 0\n",
    "        #     if i == j:\n",
    "        #         return 1\n",
    "        #     if j == 1:\n",
    "        #         return  i * (i + 1) // 2\n",
    "        #     return (2 * f(i - 1, j) + f(i - 1, j - 1) - f(i - 2, j)) % MOD\n",
    "        # return f(n - 1, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        dp = [[0 for i in range(k+1)] for i in range(n+1)]\n",
    "        for i in range(2,n+1):\n",
    "            dp[i][1] = (i-1)*i//2\n",
    "        sum_l = [0 for i in range(k+1)]\n",
    "        sum_l[1] = 1\n",
    "        for i in range(3,n+1):\n",
    "            for j in range(2,k+1):\n",
    "                dp[i][j] = (dp[i-1][j] + sum_l[j-1])%mod\n",
    "                sum_l[j-1] = (sum_l[j-1] + dp[i][j-1])%mod\n",
    "        return dp[n][k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        dp = [[0 for i in range(k+1)] for i in range(n+1)]\n",
    "        for i in range(2,n+1):\n",
    "            dp[i][1] = (i-1)*i//2\n",
    "        sum_l = [0 for i in range(k+1)]\n",
    "        sum_l[1] = 1\n",
    "        for i in range(3,n+1):\n",
    "            for j in range(2,k+1):\n",
    "                dp[i][j] = (dp[i-1][j] + sum_l[j-1])%mod\n",
    "                sum_l[j-1] = (sum_l[j-1] + dp[i][j-1])%mod\n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        # 处理不够分的情况\n",
    "        if n - 1 < k:\n",
    "            # print(\"计算:\", n, k, \"->\", 0)\n",
    "            return 0\n",
    "\n",
    "        # 处理刚好够分的情况\n",
    "        if n - 1 == k:\n",
    "            # print(\"计算:\", n, k, \"->\", 1)\n",
    "            return 1\n",
    "\n",
    "        # 处理只分成一个的情况\n",
    "        if k == 1:\n",
    "            # print(\"计算:\", n, k, \"->\", n * (n - 1) // 2)\n",
    "            return n * (n - 1) // 2\n",
    "\n",
    "        # 处理一般的情况\n",
    "\n",
    "        # 定义状态表格\n",
    "        # O(N×K)\n",
    "        dp = [[0] * n for _ in range(k)]\n",
    "\n",
    "        # 计算第一行\n",
    "        for j in range(1, n):\n",
    "            dp[0][j] = j * (j + 1) // 2\n",
    "\n",
    "        # 计算其他行\n",
    "        for i in range(1, k):\n",
    "            total = dp[i - 1][i]\n",
    "            for j in range(i + 1, n):\n",
    "                dp[i][j] = dp[i][j - 1] + total\n",
    "                total += dp[i - 1][j]\n",
    "\n",
    "        return dp[-1][-1] % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        f = [[[0] * 2 for _ in range(k + 1)] for _ in range(n)]\n",
    "\n",
    "        f[0][0][0] = 1\n",
    "        for i in range(1, n):\n",
    "            for j in range(k + 1):\n",
    "                f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1]) % MOD\n",
    "                f[i][j][1] = f[i - 1][j][1]\n",
    "                if j > 0:\n",
    "                    f[i][j][1] += f[i - 1][j - 1][0]\n",
    "                    f[i][j][1] %= MOD\n",
    "                    f[i][j][1] += f[i - 1][j - 1][1]\n",
    "                    f[i][j][1] %= MOD\n",
    "\n",
    "        return (f[n - 1][k][0] + f[n - 1][k][1]) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        f = [[[0] * 2 for _ in range(k + 1)] for _ in range(n)]\n",
    "\n",
    "        f[1][1][1] = 1\n",
    "        f[1][0][0] = 1\n",
    "        for i in range(2, n):\n",
    "            for j in range(k + 1):\n",
    "                f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1]) % MOD\n",
    "                f[i][j][1] = f[i - 1][j][1]\n",
    "                if j > 0:\n",
    "                    f[i][j][1] += f[i - 1][j - 1][0]\n",
    "                    f[i][j][1] %= MOD\n",
    "                    f[i][j][1] += f[i - 1][j - 1][1]\n",
    "                    f[i][j][1] %= MOD\n",
    "\n",
    "        return (f[n - 1][k][0] + f[n - 1][k][1]) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "\n",
    "        '''\n",
    "        f(i, j): [0, i]放置j段不重叠线段的方案数，考虑以下转移:\n",
    "        最后一个位置不使用: f(i - 1, j)\n",
    "        [i - 1, i]放一条线段：f(i - 1, j - 1)\n",
    "        [i - 2, i]放一条线段: f(i - 2, j - 1)\n",
    "        ……\n",
    "\n",
    "        f(i, j) = f(i - 1, j) + f(i - 1, j - 1) + f(i - 2, j - 1) + …… f(0, j - 1)\n",
    "同样f(i - 1, j) = f(i - 2, j) + f(i - 2, j - 1) + f(i - 3, j - 1) + …… f(0, j - 1)\n",
    "\n",
    "        相减:f(i, j) = 2 * f(i - 1, j) + f(i - 1, j - 1) - f(i - 2, j)\n",
    "        '''\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            if i < j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if j == 1:\n",
    "                return  i * (i + 1) // 2\n",
    "            return (2 * f(i - 1, j) + f(i - 1, j - 1) - f(i - 2, j)) % MOD\n",
    "        \n",
    "        return f(n - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        \"\"\"\n",
    "        dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + dp[i-2][j-1] + ... dp[i-n][j-1]\n",
    "        dp[i-1][j] = dp[i-2][j] + dp[i-2][j-1] + dp[i-3][j-1] + ... dp[i-n][j-1] + dp[i-n-1][j-1]\n",
    "        dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j] - dp[i-2][j] # 优化\n",
    "        \"\"\"\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j == 1:\n",
    "                return i*(i-1)//2\n",
    "            if i <= 1 or j >= i:\n",
    "                return 0\n",
    "            \n",
    "            res = 2*dfs(i-1, j) + dfs(i-1, j-1) - dfs(i-2, j)\n",
    "            return res % mod \n",
    "\n",
    "            \n",
    "            return res % mod\n",
    "\n",
    "        return dfs(n, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        # dp[i][j] 使用i长度构造j条线段的方案数\n",
    "        dp = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        # dp方案数的前缀和\n",
    "        pre_sum =  [[0] * (k + 1) for _ in range(n + 1)]\n",
    "\n",
    "        # 初始化,构建0条就1个方案\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i][0] = 1\n",
    "            pre_sum[i][0] = 1 + pre_sum[i - 1][0]\n",
    "\n",
    "        # 长度>=2才能构建线段,而且线段数<长度\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(1, min(k+1,i)):\n",
    "                # 新线段的右端点肯定是i,看前一个线段的右端点在哪\n",
    "                # 如果是在i-1,说明新线段只能在i-1,i上\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "                # 如果更左,那有很多种可能,要一一列举加起来\n",
    "                dp[i][j] += pre_sum[i - 1][j - 1]\n",
    "                pre_sum[i][j] = dp[i][j] + pre_sum[i - 1][j]\n",
    "\n",
    "        return dp[-1][-1] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import sys\n",
    "from functools import lru_cache\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 1000000007\n",
    "class Solution:\n",
    "    def numberOfSets(self, n: int, k: int) -> int:\n",
    "\n",
    "        '''\n",
    "        最后一个位置有两种种选择，一种是不使用，一种是和前1个并一起，和前2个并一起.....\n",
    "        dp(ii, kk) =    dp(ii-1, kk) + dp(ii-1, kk-1) + dp(ii-2, kk-1) + dp(ii-3, kk-1), ... dp(0, kk-1)\n",
    "        dp(ii-1, kk) =  dp(ii-2, kk)                  + dp(ii-2, kk-1) + dp(ii-3, kk-1), ... dp(0. kk-1)\n",
    "        上下两式相减后可得 dp(ii, kk) = 2 * dp(ii-1, kk) + dp(ii-1, kk-1) - dp(ii-2, kk)\n",
    "        '''\n",
    "\n",
    "        # 前ii个位置分kk段不重叠的方法数\n",
    "        @lru_cache(typed=False, maxsize=1280000000)\n",
    "        def dp(ii, kk):\n",
    "            if ii < kk:\n",
    "                return 0\n",
    "\n",
    "            if ii == kk:\n",
    "                return 1\n",
    "\n",
    "            if kk == 1:\n",
    "                return ii * (ii+1) // 2\n",
    "\n",
    "            return (2 * dp(ii-1, kk) + dp(ii-1, kk-1) - dp(ii-2, kk)) % MOD\n",
    "\n",
    "\n",
    "        return dp(n-1, k)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
